SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Boolean function</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Boolean function</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Binary_function" title="Binary function">Binary function</a>.</div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1246091330">

/* start https://en.wikipedia.org/ */

.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><table class="sidebar nomobile nowraplinks"><tbody><tr><th class="sidebar-title" style="font-size: 130%; margin: 6px 0px 6px 0px; background: #ddf;"><a href="Logical_connective" title="Logical connective">Logical connectives</a></th></tr><tr><td class="sidebar-content">

<mover>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \neg A,-A,{\overline {A}},\sim A}</annotation>

</semantics>

</math></span><img src="./8eab858e54d8de87e36fc80a991b32e74201a600.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:16.001ex; height:3.343ex;" alt="{\displaystyle \neg A,-A,{\overline {A}},\sim A}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_conjunction" title="Logical conjunction">AND</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}</annotation>

</semantics>

</math></span><img src="./c041e99940ccd418648ea18d200af37e2b3548d2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:33.68ex; height:2.509ex;" alt="{\displaystyle A\land B,A\cdot B,AB,A\ \&\ B,A\ \&\&\ B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Sheffer_stroke" title="Sheffer stroke">NAND</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}">

<mover>

</mover>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}</annotation>

</semantics>

</math></span><img src="./b05374b45c2316947f052c6a46ca0f1d9381ed0e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.98ex; height:3.509ex;" alt="{\displaystyle A{\overline {\land }}B,A\uparrow B,A\mid B,{\overline {A\cdot B}}}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_disjunction" title="Logical disjunction">OR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}</annotation>

</semantics>

</math></span><img src="./a262d8ab1dd1738c2b888661fe847101b624992d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.943ex; height:2.843ex;" alt="{\displaystyle A\lor B,A+B,A\mid B,A\parallel B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Logical_NOR" title="Logical NOR">NOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}">

<mover>

</mover>

</mrow>

<mover>

<mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}</annotation>

</semantics>

</math></span><img src="./331ccd940d0039678505e971d3e13a63fca14354.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.663ex; height:3.343ex;" alt="{\displaystyle A{\overline {\lor }}B,A\downarrow B,{\overline {A+B}}}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="XNOR_gate" title="XNOR gate">XNOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}">

<mover>

<mrow>

<mover>

</mover>

</mrow>

</mrow>

</mover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}</annotation>

</semantics>

</math></span><img src="./7e5a7f5c2cebe8c2903dea347e6ce9223cc47e13.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.669ex; height:3.843ex;" alt="{\displaystyle A\odot B,{\overline {A{\overline {\lor }}B}}}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> └ <a href="Logical_biconditional" title="Logical biconditional">equivalent</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}</annotation>

</semantics>

</math></span><img src="./73fd8a2bddea3e7553e1905a4b2b8944269d5430.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\equiv B,A\Leftrightarrow B,A\leftrightharpoons B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Exclusive_or" title="Exclusive or">XOR</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A{\underline {\lor }}B,A\oplus B}">

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A{\underline {\lor }}B,A\oplus B}</annotation>

</semantics>

</math></span><img src="./d48ea5022d9d865ea81c6f954cf73429be684009.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.562ex; margin-bottom: -0.776ex; width:12.441ex; height:3.176ex;" alt="{\displaystyle A{\underline {\lor }}B,A\oplus B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> └ nonequivalent</td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}</annotation>

</semantics>

</math></span><img src="./e31480781c46a0001e81f596615bc56e20d8aaa6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \equiv B,A\not \Leftrightarrow B,A\nleftrightarrow B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Material_conditional" title="Material conditional">implies</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}</annotation>

</semantics>

</math></span><img src="./da2d4ee4d40286755cb17f11743dcece3224fa90.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\Rightarrow B,A\supset B,A\rightarrow B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Material_nonimplication" title="Material nonimplication">nonimplication</a> (<a href="NIMPLY_gate" title="NIMPLY gate">NIMPLY</a>)</td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}</annotation>

</semantics>

</math></span><img src="./4d66f3ed3dc468f35292dfe91a75d59b3b5d4915.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \Rightarrow B,A\not \supset B,A\nrightarrow B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Converse_(logic)" title="Converse (logic)">converse</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}</annotation>

</semantics>

</math></span><img src="./128eb93aed65dd2e3aa1a4aaef4171a44f9a6718.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:22.916ex; height:2.509ex;" alt="{\displaystyle A\Leftarrow B,A\subset B,A\leftarrow B}" loading="lazy"></span></td></tr><tr style="vertical-align:top"><td style="text-align:left;"> <a href="Converse_nonimplication" title="Converse nonimplication">converse nonimplication</a></td><td style="text-align:right;font-size:125%;line-height:0.8em;vertical-align:middle;white-space:nowrap;font-family:serif;"> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}</annotation>

</semantics>

</math></span><img src="./651dce7a12fa2331a8c610ee47b32982552a01f4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.917ex; height:2.676ex;" alt="{\displaystyle A\not \Leftarrow B,A\not \subset B,A\nleftarrow B}" loading="lazy"></span></td></tr></tbody></table></td>

</tr><tr><th class="sidebar-heading" style="background: #eef; text-align: center;">

Related concepts</th></tr><tr><td class="sidebar-content">

<div class="hlist" style="line-height:1.3em;"><ul><li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li><li><a href="First-order_logic" title="First-order logic">Predicate logic</a></li><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li><li><a href="Truth_table" title="Truth table">Truth table</a></li><li><a href="Truth_function" title="Truth function">Truth function</a></li><li><a href="Functional_completeness" title="Functional completeness">Functional completeness</a></li><li><a href="Scope_(logic)" title="Scope (logic)">Scope (logic)</a></li></ul></div></td>

</tr><tr><th class="sidebar-heading" style="background: #eef; text-align: center;">

Applications</th></tr><tr><td class="sidebar-content">

<div class="hlist"><ul><li><a href="Logic_gate" title="Logic gate">Digital logic</a></li><li><a href="Programming_language" title="Programming language">Programming languages</a></li><li><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></li><li><a href="Philosophy_of_logic" title="Philosophy of logic">Philosophy of logic</a></li></ul></div></td>

</tr><tr><td class="sidebar-below hlist" style="background: #eef; text-align: center;">

<span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</td></tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></td></tr></tbody></table>

<p>In <a href="Mathematics" title="Mathematics">mathematics</a>, a <b>Boolean function</b> is a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> whose <a href="Argument_of_a_function" title="Argument of a function">arguments</a> and result assume values from a two-element set (usually {true, false}, {0,1} or {−1,1}).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Alternative names are <b>switching function</b>, used especially in older <a href="Computer_science" title="Computer science">computer science</a> literature,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> and <b><a href="Truth_function" title="Truth function">truth function</a></b> (or <b>logical function)</b>, used in <a href="Logic" title="Logic">logic</a>. Boolean functions are the subject of <a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a> and <a href="Switching_theory" class="mw-redirect" title="Switching theory">switching theory</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>A Boolean function takes the form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{k}\to \{0,1\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{k}\to \{0,1\}}</annotation>

</semantics>

</math></span><img src="./e4aed3e0000bf00e545c1250ae63f4b1e9275abf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.286ex; height:3.176ex;" alt="{\displaystyle f:\{0,1\}^{k}\to \{0,1\}}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}}</annotation>

</semantics>

</math></span><img src="./28de5781698336d21c9c560fb1cbb3fb406923eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.684ex; height:2.843ex;" alt="{\displaystyle \{0,1\}}" loading="lazy"></span> is known as the <a href="Boolean_domain" title="Boolean domain">Boolean domain</a> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> is a non-negative integer called the <a href="Arity" title="Arity">arity</a> of the function. In the case where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=0}</annotation>

</semantics>

</math></span><img src="./6307c8a99dad7d0bcb712352ae0a748bd99a038b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.472ex; height:2.176ex;" alt="{\displaystyle k=0}" loading="lazy"></span>, the function is a constant element of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}}</annotation>

</semantics>

</math></span><img src="./28de5781698336d21c9c560fb1cbb3fb406923eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.684ex; height:2.843ex;" alt="{\displaystyle \{0,1\}}" loading="lazy"></span>. A Boolean function with multiple outputs, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}</annotation>

</semantics>

</math></span><img src="./0f373a3870180d8a7b007bb937595cd3f3f01d44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.961ex; height:3.176ex;" alt="{\displaystyle f:\{0,1\}^{k}\to \{0,1\}^{m}}" loading="lazy"></span> with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle m>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle m>1}</annotation>

</semantics>

</math></span><img src="./7f27527902d05e4c32bcbe28d425d7790f8ae191.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.301ex; height:2.176ex;" alt="{\displaystyle m>1}" loading="lazy"></span> is a <b>vectorial</b> or <i>vector-valued</i> Boolean function (an <a href="S-box" title="S-box">S-box</a> in symmetric <a href="Cryptography" title="Cryptography">cryptography</a>).<sup id="cite_ref-:2_6-0" class="reference"><a href="#cite_note-:2-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p><p>There are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{2^{k}}}">

<msup>

<msup>

</mrow>

</msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{2^{k}}}</annotation>

</semantics>

</math></span><img src="./3156c862b1003597795baa0f0698d6e9fd0cfe8f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.076ex; height:3.009ex;" alt="{\displaystyle 2^{2^{k}}}" loading="lazy"></span> different Boolean functions with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> arguments; equal to the number of different <a href="Truth_table" title="Truth table">truth tables</a> with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation>

</semantics>

</math></span><img src="./2d82641ae2702b0db07dd11830af27b9ee0cd196.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}" loading="lazy"></span> entries.

</p><p>Every <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span>-ary Boolean function can be expressed as a <a href="Propositional_formula" title="Propositional formula">propositional formula</a> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k}</annotation>

</semantics>

</math></span><img src="./c3c9a2c7b599b37105512c5d570edc034056dd40.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}" loading="lazy"></span> variables <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},...,x_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},...,x_{k}}</annotation>

</semantics>

</math></span><img src="./2b83bf0a25e29a5395cc534f35edc8fa7e2d18ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.972ex; height:2.009ex;" alt="{\displaystyle x_{1},...,x_{k}}" loading="lazy"></span>, and two propositional formulas are <a href="Logical_equivalence" title="Logical equivalence">logically equivalent</a> if and only if they express the same Boolean function.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Truth_table" title="Truth table">Truth table</a> and <a href="Truth_function" title="Truth function">Truth function</a></div>

<p>The rudimentary symmetric Boolean functions (<a href="Logical_connective" title="Logical connective">logical connectives</a> or <a href="Logic_gate" title="Logic gate">logic gates</a>) are:

</p>

<ul><li><a href="Inverter_(logic_gate)" title="Inverter (logic gate)">NOT</a>, <a href="Negation" title="Negation">negation</a> or <a href="Logical_complement" class="mw-redirect" title="Logical complement">complement</a> - which receives one input and returns true when that input is false ("not")</li>

<li><a href="AND_gate" title="AND gate">AND</a> or <a href="Logical_conjunction" title="Logical conjunction">conjunction</a> - true when all inputs are true ("both")</li>

<li><a href="OR_gate" title="OR gate">OR</a> or <a href="Logical_disjunction" title="Logical disjunction">disjunction</a> - true when any input is true ("either")</li>

<li><a href="XOR_gate" title="XOR gate">XOR</a> or <a href="Exclusive_or" title="Exclusive or">exclusive disjunction</a> - true when one of its inputs is true and the other is false ("not equal")</li>

<li><a href="NAND_gate" title="NAND gate">NAND</a> or <a href="Sheffer_stroke" title="Sheffer stroke">Sheffer stroke</a> - true when it is not the case that all inputs are true ("not both")</li>

<li><a href="NOR_gate" title="NOR gate">NOR</a> or <a href="Logical_NOR" title="Logical NOR">logical nor</a> - true when none of the inputs are true ("neither")</li>

<li><a href="XNOR_gate" title="XNOR gate">XNOR</a> or <a href="Logical_equality" title="Logical equality">logical equality</a> - true when both inputs are the same ("equal")</li></ul>

<p>An example of a more complicated function is the <a href="Majority_function" title="Majority function">majority function</a> (of an odd number of inputs).

</p>

<div class="mw-heading mw-heading2"><h2 id="Representation">Representation</h2></div>

<p>A Boolean function may be specified in a variety of ways:

</p>

<ul><li><a href="Truth_table" title="Truth table">Truth table</a>: explicitly listing its value for all possible values of the arguments

<ul><li>Marquand diagram: truth table values arranged in a two-dimensional grid (used in a <a href="Karnaugh_map" title="Karnaugh map">Karnaugh map</a>)</li>

<li><a href="Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a>, listing the truth table values at the bottom of a binary tree</li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a>, depicting the truth table values as a colouring of regions of the plane</li></ul></li></ul>

<p>Algebraically, as a <a href="Propositional_formula" title="Propositional formula">propositional formula</a> using rudimentary Boolean functions:

</p>

<ul><li><a href="Negation_normal_form" title="Negation normal form">Negation normal form</a>, an arbitrary mix of AND and ORs of the arguments and their complements</li>

<li><a href="Disjunctive_normal_form" title="Disjunctive normal form">Disjunctive normal form</a>, as an OR of ANDs of the arguments and their complements</li>

<li><a href="Conjunctive_normal_form" title="Conjunctive normal form">Conjunctive normal form</a>, as an AND of ORs of the arguments and their complements</li>

<li><a href="Canonical_normal_form" title="Canonical normal form">Canonical normal form</a>, a standardized formula which uniquely identifies the function:

<ul><li><a href="Algebraic_normal_form" title="Algebraic normal form">Algebraic normal form</a> or <a href="Zhegalkin_polynomial" title="Zhegalkin polynomial">Zhegalkin polynomial</a>, as a XOR of ANDs of the arguments (no complements allowed)</li>

<li><i>Full</i> (canonical) <a href="Disjunctive_normal_form" title="Disjunctive normal form">disjunctive normal form</a>, an OR of ANDs each containing every argument or complement (<a href="Minterms" class="mw-redirect" title="Minterms">minterms</a>)</li>

<li><i>Full</i> (canonical) <a href="Conjunctive_normal_form" title="Conjunctive normal form">conjunctive normal form</a>, an AND of ORs each containing every argument or complement (<a href="Maxterms" class="mw-redirect" title="Maxterms">maxterms</a>)</li>

<li><a href="Blake_canonical_form" title="Blake canonical form">Blake canonical form</a>, the OR of all the <a href="Prime_implicant" class="mw-redirect" title="Prime implicant">prime implicants</a> of the function</li></ul></li></ul>

<p>Boolean formulas can also be displayed as a graph:

</p>

<ul><li><a href="Propositional_directed_acyclic_graph" title="Propositional directed acyclic graph">Propositional directed acyclic graph</a>

<ul><li><a href="Circuit_(computer_science)" title="Circuit (computer science)">Digital circuit</a> diagram of <a href="Logic_gate" title="Logic gate">logic gates</a>, a <a href="Boolean_circuit" title="Boolean circuit">Boolean circuit</a></li>

<li><a href="And-inverter_graph" title="And-inverter graph">And-inverter graph</a>, using only AND and NOT</li></ul></li></ul>

<p>In order to optimize electronic circuits, Boolean formulas can be <a href="Minimization_of_Boolean_functions" class="mw-redirect" title="Minimization of Boolean functions">minimized</a> using the <a href="Quine%E2%80%93McCluskey_algorithm" title="Quine–McCluskey algorithm">Quine–McCluskey algorithm</a> or <a href="Karnaugh_map" title="Karnaugh map">Karnaugh map</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Analysis">Analysis</h2></div>

<div role="note" class="hatnote navigation-not-searchable">See also: <a href="Analysis_of_Boolean_functions" title="Analysis of Boolean functions">Analysis of Boolean functions</a></div>

<div class="mw-heading mw-heading3"><h3 id="Properties">Properties</h3></div>

<p>A Boolean function can have a variety of properties:<sup id="cite_ref-:0_7-0" class="reference"><a href="#cite_note-:0-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Constant_function" title="Constant function">Constant</a>: Is always true or always false regardless of its arguments.</li>

<li><a href="Monotonic_function#In_Boolean_functions" title="Monotonic function">Monotone</a>: for every combination of argument values, changing an argument from false to true can only cause the output to switch from false to true and not from true to false. A function is said to be <a href="Unate_function" title="Unate function">unate</a> in a certain variable if it is monotone with respect to changes in that variable.</li>

<li><a href="Linearity#Boolean_functions" title="Linearity">Linear</a>: for each variable, flipping the value of the variable either always makes a difference in the truth value or never makes a difference (a <a href="Parity_function" title="Parity function">parity function</a>).</li>

<li><a href="Symmetric_Boolean_function" title="Symmetric Boolean function">Symmetric</a>: the value does not depend on the order of its arguments.</li>

<li><a href="Read-once_function" title="Read-once function">Read-once</a>: Can be expressed with <a href="Logical_conjunction" title="Logical conjunction">conjunction</a>, <a href="Logical_disjunction" title="Logical disjunction">disjunction</a>, and <a href="Negation" title="Negation">negation</a> with a single instance of each variable.</li>

<li><a href="Balanced_Boolean_function" title="Balanced Boolean function">Balanced</a>: if its <a href="Truth_table" title="Truth table">truth table</a> contains an equal number of zeros and ones. The <a href="Hamming_weight" title="Hamming weight">Hamming weight</a> of the function is the number of ones in the truth table.</li>

<li><a href="Bent_function" title="Bent function">Bent</a>: its derivatives are all balanced (the autocorrelation spectrum is zero)</li>

<li><a href="Correlation_immunity" title="Correlation immunity">Correlation immune</a> to <i>m</i>th order: if the output is uncorrelated with all (linear) combinations of at most <i>m</i> arguments</li>

<li><a href="Evasive_Boolean_function" title="Evasive Boolean function">Evasive</a>: if evaluation of the function always requires the value of all arguments</li>

<li>A Boolean function is a <i>Sheffer function</i> if it can be used to create (by composition) any arbitrary Boolean function (see <a href="Functional_completeness" title="Functional completeness">functional completeness</a>)</li>

<li>The <i>algebraic degree</i> of a function is the order of the highest order monomial in its <a href="Algebraic_normal_form" title="Algebraic normal form">algebraic normal form</a></li></ul>

<p><a href="Circuit_complexity" title="Circuit complexity">Circuit complexity</a> attempts to classify Boolean functions with respect to the size or depth of circuits that can compute them.

</p>

<div class="mw-heading mw-heading3"><h3 id="Derived_functions">Derived functions</h3></div>

<p>A Boolean function may be decomposed using <a href="Boole's_expansion_theorem" title="Boole's expansion theorem">Boole's expansion theorem</a> in positive and negative <i>Shannon</i> <i>cofactors</i> (<a href="Shannon_expansion" class="mw-redirect" title="Shannon expansion">Shannon expansion</a>), which are the (<i>k</i>−1)-ary functions resulting from fixing one of the arguments (to 0 or 1). The general <i>k</i>-ary functions obtained by imposing a linear constraint on a set of inputs (a linear subspace) are known as <i>subfunctions</i>.<sup id="cite_ref-:1_8-0" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>The <i><a href="Boolean_derivative" class="mw-redirect" title="Boolean derivative">Boolean derivative</a></i> of the function to one of the arguments is a (<i>k</i>−1)-ary function that is true when the output of the function is sensitive to the chosen input variable; it is the XOR of the two corresponding cofactors. A derivative and a cofactor are used in a <a href="Reed%E2%80%93Muller_expansion" title="Reed–Muller expansion">Reed–Muller expansion</a>. The concept can be generalized as a <i>k</i>-ary derivative in the direction dx, obtained as the difference (XOR) of the function at x and x + dx.<sup id="cite_ref-:1_8-1" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>The <i><a href="Zhegalkin_polynomial#Möbius_transformation" title="Zhegalkin polynomial">Möbius transform</a></i> (or <i>Boole–Möbius transform</i>) of a Boolean function is the set of coefficients of its <a href="Zhegalkin_polynomial" title="Zhegalkin polynomial">polynomial</a> (<a href="Algebraic_normal_form" title="Algebraic normal form">algebraic normal form</a>), as a function of the monomial exponent vectors. It is a <a href="Involution_(mathematics)" title="Involution (mathematics)">self-inverse</a> transform. It can be calculated efficiently using a <a href="Butterfly_diagram" title="Butterfly diagram">butterfly algorithm</a> ("<i>Fast Möbius Transform</i>"), analogous to the <a href="Fast_Fourier_transform" title="Fast Fourier transform">fast Fourier transform</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> <i>Coincident</i> Boolean functions are equal to their Möbius transform, i.e. their truth table (minterm) values equal their algebraic (monomial) coefficients.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> There are 2^2^(<i>k</i>−1) coincident functions of <i>k</i> arguments.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Cryptographic_analysis">Cryptographic analysis</h3></div>

<p>The <i><a href="Walsh_transform" class="mw-redirect" title="Walsh transform">Walsh transform</a></i> of a Boolean function is a k-ary integer-valued function giving the coefficients of a decomposition into <a href="Parity_function" title="Parity function">linear functions</a> (<a href="Walsh_function" title="Walsh function">Walsh functions</a>), analogous to the decomposition of real-valued functions into <a href="Harmonic" title="Harmonic">harmonics</a> by the <a href="Fourier_transform" title="Fourier transform">Fourier transform</a>. Its square is the <i>power spectrum</i> or <i>Walsh spectrum</i>. The Walsh coefficient of a single bit vector is a measure for the correlation of that bit with the output of the Boolean function. The maximum (in absolute value) Walsh coefficient is known as the <i>linearity</i> of the function.<sup id="cite_ref-:1_8-2" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The highest number of bits (order) for which all Walsh coefficients are 0 (i.e. the subfunctions are balanced) is known as <i>resiliency</i>, and the function is said to be <a href="Correlation_immunity" title="Correlation immunity">correlation immune</a> to that order.<sup id="cite_ref-:1_8-3" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> The Walsh coefficients play a key role in <a href="Linear_cryptanalysis" title="Linear cryptanalysis">linear cryptanalysis</a>.

</p><p>The <i><a href="Autocorrelation" title="Autocorrelation">autocorrelation</a></i> of a Boolean function is a k-ary integer-valued function giving the correlation between a certain set of changes in the inputs and the function output. For a given bit vector it is related to the Hamming weight of the derivative in that direction. The maximal autocorrelation coefficient (in absolute value) is known as the <i>absolute indicator</i>.<sup id="cite_ref-:0_7-1" class="reference"><a href="#cite_note-:0-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:1_8-4" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> If all autocorrelation coefficients are 0 (i.e. the derivatives are balanced) for a certain number of bits then the function is said to satisfy the <i>propagation criterion</i> to that order; if they are all zero then the function is a <a href="Bent_function" title="Bent function">bent function</a>.<sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> The autocorrelation coefficients play a key role in <a href="Differential_cryptanalysis" title="Differential cryptanalysis">differential cryptanalysis</a>.

</p><p>The Walsh coefficients of a Boolean function and its autocorrelation coefficients are related by the equivalent of the <a href="Wiener%E2%80%93Khinchin_theorem" title="Wiener–Khinchin theorem">Wiener–Khinchin theorem</a>, which states that the autocorrelation and the power spectrum are a Walsh transform pair.<sup id="cite_ref-:1_8-5" class="reference"><a href="#cite_note-:1-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Linear_approximation_table">Linear approximation table</h4></div>

<p>These concepts can be extended naturally to <i>vectorial</i> Boolean functions by considering their output bits (<i>coordinates</i>) individually, or more thoroughly, by looking at the set of all linear functions of output bits, known as its <i>components</i>.<sup id="cite_ref-:2_6-1" class="reference"><a href="#cite_note-:2-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> The set of Walsh transforms of the components is known as a <b>linear approximation table</b> (LAT)<sup id="cite_ref-:3_13-0" class="reference"><a href="#cite_note-:3-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:4_14-0" class="reference"><a href="#cite_note-:4-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> or <i>correlation matrix</i>;<sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-16" class="reference"><a href="#cite_note-16"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> it describes the correlation between different linear combinations of input and output bits. The set of autocorrelation coefficients of the components is the <i>autocorrelation table</i>,<sup id="cite_ref-:4_14-1" class="reference"><a href="#cite_note-:4-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> related by a Walsh transform of the components<sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> to the more widely used <i>difference distribution table</i> (DDT)<sup id="cite_ref-:3_13-1" class="reference"><a href="#cite_note-:3-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:4_14-2" class="reference"><a href="#cite_note-:4-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> which lists the correlations between differences in input and output bits (see also: <a href="S-box" title="S-box">S-box</a>).

</p>

<div class="mw-heading mw-heading2"><h2 id="Real_polynomial_form">Real polynomial form</h2></div>

<div class="mw-heading mw-heading3"><h3 id="On_the_unit_hypercube">On the unit hypercube</h3></div>

<p>Any Boolean function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}</annotation>

</semantics>

</math></span><img src="./80e184b0ffec671b7b0aab8a379a0635d5611939.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.555ex; height:2.843ex;" alt="{\displaystyle f(x):\{0,1\}^{n}\rightarrow \{0,1\}}" loading="lazy"></span> can be uniquely extended (interpolated) to the <a href="Real_number" title="Real number">real domain</a> by a <a href="Multilinear_polynomial" title="Multilinear polynomial">multilinear polynomial</a> in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {R} ^{n}}</annotation>

</semantics>

</math></span><img src="./c510b63578322050121fe966f2e5770bea43308d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.897ex; height:2.343ex;" alt="{\displaystyle \mathbb {R} ^{n}}" loading="lazy"></span>, constructed by summing the truth table values multiplied by <a href="Lagrange_polynomial" title="Lagrange polynomial">indicator polynomials</a>:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}(x)=\sum _{a\in {\{0,1\}}^{n}}f(a)\prod _{i:a_{i}=1}x_{i}\prod _{i:a_{i}=0}(1-x_{i})}</annotation>

</semantics>

</math></span></span>For example, the extension of the binary XOR function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\oplus y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\oplus y}</annotation>

</semantics>

</math></span><img src="./10fc94462e7622639c0c464161a1f0c8fc057999.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.326ex; height:2.343ex;" alt="{\displaystyle x\oplus y}" loading="lazy"></span> is<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0(1-x)(1-y)+1x(1-y)+1(1-x)y+0xy}</annotation>

</semantics>

</math></span></span>which equals<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+y-2xy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+y-2xy}</annotation>

</semantics>

</math></span></span>Some other examples are negation (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-x}</annotation>

</semantics>

</math></span><img src="./0ba56b3b25228e75d307b633671555b5f2777468.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.333ex; height:2.343ex;" alt="{\displaystyle 1-x}" loading="lazy"></span>), AND (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle xy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle xy}</annotation>

</semantics>

</math></span><img src="./c72eb345e496513fb8b2fa4aa8c4d89b855f9a01.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.485ex; height:2.009ex;" alt="{\displaystyle xy}" loading="lazy"></span>) and OR (<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x+y-xy}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x+y-xy}</annotation>

</semantics>

</math></span><img src="./f62962fe7941173de8ed40adc639c194abe59adb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.651ex; height:2.343ex;" alt="{\displaystyle x+y-xy}" loading="lazy"></span>). When all operands are independent (share no variables) a function's polynomial form can be found by repeatedly applying the polynomials of the operators in a Boolean formula. When the coefficients are calculated <a href="Modular_arithmetic" title="Modular arithmetic">modulo 2</a> one obtains the <a href="Algebraic_normal_form" title="Algebraic normal form">algebraic normal form</a> (<a href="Zhegalkin_polynomial" title="Zhegalkin polynomial">Zhegalkin polynomial</a>).

</p><p>Direct expressions for the coefficients of the polynomial can be derived by taking an appropriate derivative:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}">

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{array}{lcl}f^{*}(00)&=&(f^{*})(00)&=&f(00)\\f^{*}(01)&=&(\partial _{1}f^{*})(00)&=&-f(00)+f(01)\\f^{*}(10)&=&(\partial _{2}f^{*})(00)&=&-f(00)+f(10)\\f^{*}(11)&=&(\partial _{1}\partial _{2}f^{*})(00)&=&f(00)-f(01)-f(10)+f(11)\\\end{array}}}</annotation>

</semantics>

</math></span></span>this generalizes as the <a href="M%C3%B6bius_transform" class="mw-redirect" title="Möbius transform">Möbius inversion</a> of the <a href="Partially_ordered_set" title="Partially ordered set">partially ordered set</a> of bit vectors:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}">

<msup>

</mrow>

</msup>

</mrow>

</munder>

<msup>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}(m)=\sum _{a\subseteq m}(-1)^{|a|+|m|}f(a)}</annotation>

</semantics>

</math></span></span>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |a|}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |a|}</annotation>

</semantics>

</math></span><img src="./8b61d5baa05004815f3abc52f517ce62b609b9b6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.523ex; height:2.843ex;" alt="{\displaystyle |a|}" loading="lazy"></span> denotes the weight of the bit vector <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>. Taken modulo 2, this is the <a href="Zhegalkin_polynomial" title="Zhegalkin polynomial">Boolean <i>Möbius transform</i></a>, giving the <a href="Algebraic_normal_form" title="Algebraic normal form">algebraic normal form</a> coefficients:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}">

<mover>

</mover>

</mrow>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\hat {f}}(m)=\bigoplus _{a\subseteq m}f(a)}</annotation>

</semantics>

</math></span></span>In both cases, the sum is taken over all bit-vectors <i>a</i> covered by <i>m</i>, i.e. the "one" bits of <i>a</i> form a subset of the one bits of <i>m</i>.

</p><p>When the domain is restricted to the n-dimensional <a href="Hypercube" title="Hypercube">hypercube</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,1]^{n}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [0,1]^{n}}</annotation>

</semantics>

</math></span><img src="./40160923273b7109968df994dca832b91d957bf2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.871ex; height:2.843ex;" alt="{\displaystyle [0,1]^{n}}" loading="lazy"></span>, the polynomial <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}</annotation>

</semantics>

</math></span><img src="./554f08adec943929e4ea54fd275edebee5aeaaa6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.589ex; height:2.843ex;" alt="{\displaystyle f^{*}(x):[0,1]^{n}\rightarrow [0,1]}" loading="lazy"></span> gives the probability of a positive outcome when the Boolean function <i>f</i> is applied to <i>n</i> independent random (<a href="Bernoulli_distribution" title="Bernoulli distribution">Bernoulli</a>) variables, with individual probabilities <i>x</i>. A special case of this fact is the <a href="Piling-up_lemma" title="Piling-up lemma">piling-up lemma</a> for <a href="Parity_function" title="Parity function">parity functions</a>. The polynomial form of a Boolean function can also be used as its natural extension to <a href="Fuzzy_logic" title="Fuzzy logic">fuzzy logic</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="On_the_symmetric_hypercube">On the symmetric hypercube</h3></div>

<p>Often, the Boolean domain is taken as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{-1,1\}}</annotation>

</semantics>

</math></span><img src="./c0ffb8c7a09dad8456eee3669ee9a7e462fe3c34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.492ex; height:2.843ex;" alt="{\displaystyle \{-1,1\}}" loading="lazy"></span>, with false ("0") mapping to 1 and true ("1") to −1 (see <a href="Analysis_of_Boolean_functions" title="Analysis of Boolean functions">Analysis of Boolean functions</a>). The polynomial corresponding to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}</annotation>

</semantics>

</math></span><img src="./061dd928fda3d6b0af9044e19a60b3e636d30c4d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.008ex; height:2.843ex;" alt="{\displaystyle g(x):\{-1,1\}^{n}\rightarrow \{-1,1\}}" loading="lazy"></span> is then given by:<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mfrac>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle g^{*}(x)=\sum _{a\in {\{-1,1\}}^{n}}g(a)\prod _{i:a_{i}=-1}{\frac {1-x_{i}}{2}}\prod _{i:a_{i}=1}{\frac {1+x_{i}}{2}}}</annotation>

</semantics>

</math></span></span>Using the symmetric Boolean domain simplifies certain aspects of the <a href="Analysis_of_Boolean_functions" title="Analysis of Boolean functions">analysis</a>, since negation corresponds to multiplying by −1 and <a href="Parity_function" title="Parity function">linear functions</a> are <a href="Monomial" title="Monomial">monomials</a> (XOR is multiplication). This polynomial form thus corresponds to the <i>Walsh transform</i> (in this context also known as <i>Fourier transform</i>) of the function (see above). The polynomial also has the same statistical interpretation as the one in the standard Boolean domain, except that it now deals with the expected values <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}</annotation>

</semantics>

</math></span><img src="./861b6e822243c1e29474ebfe4821cd7a2147014d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:42.205ex; height:2.843ex;" alt="{\displaystyle E(X)=P(X=1)-P(X=-1)\in [-1,1]}" loading="lazy"></span> (see <a href="Piling-up_lemma" title="Piling-up lemma">piling-up lemma</a> for an example).

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>Boolean functions play a basic role in questions of <a href="Computational_complexity_theory" title="Computational complexity theory">complexity theory</a> as well as the design of processors for <a href="Digital_computer" class="mw-redirect" title="Digital computer">digital computers</a>, where they are implemented in electronic circuits using <a href="Logic_gate" title="Logic gate">logic gates</a>.

</p><p>The properties of Boolean functions are critical in <a href="Cryptography" title="Cryptography">cryptography</a>, particularly in the design of <a href="Symmetric_key_algorithm" class="mw-redirect" title="Symmetric key algorithm">symmetric key algorithms</a> (see <a href="Substitution_box" class="mw-redirect" title="Substitution box">substitution box</a>).

</p><p>In <a href="Cooperative_game_theory" title="Cooperative game theory">cooperative game</a> theory, monotone Boolean functions are called <b>simple games</b> (voting games); this notion is applied to solve problems in <a href="Social_choice_theory" title="Social choice theory">social choice theory</a>.

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}

/* end https://en.wikipedia.org/ */

</style>

/* start https://en.wikipedia.org/ */

.mw-parser-output .div-col{margin-top:0.3em;column-width:30em}.mw-parser-output .div-col-small{font-size:90%}.mw-parser-output .div-col-rules{column-rule:1px solid #aaa}.mw-parser-output .div-col dl,.mw-parser-output .div-col ol,.mw-parser-output .div-col ul{margin-top:0}.mw-parser-output .div-col li,.mw-parser-output .div-col dd{page-break-inside:avoid;break-inside:avoid-column}

/* end https://en.wikipedia.org/ */

</style><div class="div-col">

<ul><li><a href="Pseudo-Boolean_function" title="Pseudo-Boolean function">Pseudo-Boolean function</a></li>

<li><a href="Boolean-valued_function" title="Boolean-valued function">Boolean-valued function</a></li>

<li><a href="List_of_Boolean_algebra_topics" title="List of Boolean algebra topics">Boolean algebra topics</a></li>

<li><a href="Algebra_of_sets" title="Algebra of sets">Algebra of sets</a></li>

<li><a href="Decision_tree_model" title="Decision tree model">Decision tree model</a></li>

<li><a href="Indicator_function" title="Indicator function">Indicator function</a></li>

<li><a href="Signed_set" title="Signed set">Signed set</a></li></ul>

</div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://encyclopediaofmath.org/wiki/Boolean_function">"Boolean function - Encyclopedia of Mathematics"</a>. <i>encyclopediaofmath.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-03</span></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFWeisstein" class="citation web cs1">Weisstein, Eric W. <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/BooleanFunction.html">"Boolean Function"</a>. <i>mathworld.wolfram.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-03</span></span>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://encyclopedia2.thefreedictionary.com/switching+function">"switching function"</a>. <i>TheFreeDictionary.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-03</span></span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFDavies1957" class="citation journal cs1">Davies, D. W. (December 1957). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://ieeexplore.ieee.org/document/5222038">"Switching Functions of Three Variables"</a></span>. <i>IRE Transactions on Electronic Computers</i>. <b>EC-6</b> (4): <span class="nowrap">265–</span>275. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTEC.1957.5222038">10.1109/TEC.1957.5222038</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0367-9950">0367-9950</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFMcCluskey2003" class="citation cs2">McCluskey, Edward J. (2003-01-01), <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.5555/1074100.1074844">"Switching theory"</a>, <i>Encyclopedia of Computer Science</i>, GBR: John Wiley and Sons Ltd., pp. <span class="nowrap">1727–</span>1731, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-470-86412-8</bdi><span class="reference-accessdate">, retrieved <span class="nowrap">2021-05-03</span></span></cite></span>

</li>

<li id="cite_note-:2-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-:2_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:2_6-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFCarlet" class="citation web cs1">Carlet, Claude. <a rel="nofollow" class="external text" href="https://www.math.univ-paris13.fr/~carlet/chap-vectorial-fcts-corr.pdf">"Vectorial Boolean Functions for Cryptography"</a> <span class="cs1-format">(PDF)</span>. <i>University of Paris</i>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160117102533/http://www.math.univ-paris13.fr:80/~carlet/chap-vectorial-fcts-corr.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2016-01-17.</cite></span>

</li>

<li id="cite_note-:0-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/boolean_function.html">"Boolean functions — Sage 9.2 Reference Manual: Cryptography"</a>. <i>doc.sagemath.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-01</span></span>.</cite></span>

</li>

<li id="cite_note-:1-8"><span class="mw-cite-backlink">^ <a href="#cite_ref-:1_8-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:1_8-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:1_8-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-:1_8-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-:1_8-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-:1_8-5"><sup><i><b>f</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFTarannikovKorolevBotev2001" class="citation book cs1">Tarannikov, Yuriy; Korolev, Peter; Botev, Anton (2001). "Autocorrelation Coefficients and Correlation Immunity of Boolean Functions". In Boyd, Colin (ed.). <i>Advances in Cryptology — ASIACRYPT 2001</i>. Lecture Notes in Computer Science. Vol. 2248. Berlin, Heidelberg: Springer. pp. <span class="nowrap">460–</span>479. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-45682-1_27">10.1007/3-540-45682-1_27</a></span>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-45682-7</bdi>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFCarlet2010" class="citation cs2">Carlet, Claude (2010), <a rel="nofollow" class="external text" href="https://www.math.univ-paris13.fr/~carlet/chap-fcts-Bool-corr.pdf">"Boolean Functions for Cryptography and Error-Correcting Codes"</a> <span class="cs1-format">(PDF)</span>, <i>Boolean Models and Methods in Mathematics, Computer Science, and Engineering</i>, Encyclopedia of Mathematics and its Applications, Cambridge: Cambridge University Press, pp. <span class="nowrap">257–</span>397, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-84752-0</bdi><span class="reference-accessdate">, retrieved <span class="nowrap">2021-05-17</span></span></cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFPieprzykWangZhang2011" class="citation journal cs1">Pieprzyk, Josef; Wang, Huaxiong; Zhang, Xian-Mo (2011-05-01). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://doi.org/10.1080/00207160.2010.509428">"Mobius transforms, coincident Boolean functions and non-coincidence property of Boolean functions"</a></span>. <i>International Journal of Computer Mathematics</i>. <b>88</b> (7): <span class="nowrap">1398–</span>1416. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F00207160.2010.509428">10.1080/00207160.2010.509428</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0020-7160">0020-7160</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9580510">9580510</a>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFNitajSusiloTonien2017" class="citation journal cs1">Nitaj, Abderrahmane; Susilo, Willy; Tonien, Joseph (2017-10-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/s12190-016-1037-4">"Dirichlet product for boolean functions"</a>. <i>Journal of Applied Mathematics and Computing</i>. <b>55</b> (1): <span class="nowrap">293–</span>312. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs12190-016-1037-4">10.1007/s12190-016-1037-4</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1865-2085">1865-2085</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:16760125">16760125</a>.</cite></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFCanteautCarletCharpinFontaine2000" class="citation journal cs1">Canteaut, Anne; Carlet, Claude; Charpin, Pascale; Fontaine, Caroline (2000-05-14). <a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.5555/1756169.1756219">"Propagation characteristics and correlation-immunity of highly nonlinear boolean functions"</a>. <i>Proceedings of the 19th International Conference on Theory and Application of Cryptographic Techniques</i>. EUROCRYPT'00. Bruges, Belgium: Springer-Verlag: <span class="nowrap">507–</span>522. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-67517-4</bdi>.</cite></span>

</li>

<li id="cite_note-:3-13"><span class="mw-cite-backlink">^ <a href="#cite_ref-:3_13-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:3_13-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFHeys" class="citation web cs1">Heys, Howard M. <a rel="nofollow" class="external text" href="http://www.cs.bc.edu/~straubin/crypto2017/heys.pdf">"A Tutorial on Linear and Differential Cryptanalysis"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170517014157/http://www.cs.bc.edu:80/~straubin/crypto2017/heys.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2017-05-17.</cite></span>

</li>

<li id="cite_note-:4-14"><span class="mw-cite-backlink">^ <a href="#cite_ref-:4_14-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:4_14-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-:4_14-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://doc.sagemath.org/html/en/reference/cryptography/sage/crypto/sbox.html">"S-Boxes and Their Algebraic Representations — Sage 9.2 Reference Manual: Cryptography"</a>. <i>doc.sagemath.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2021-05-04</span></span>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite id="CITEREFDaemenGovaertsVandewalle1994" class="citation conference cs1">Daemen, Joan; Govaerts, René; Vandewalle, Joos (1994). "Correlation matrices". In Preneel, Bart (ed.). <i>Fast Software Encryption: Second International Workshop. Leuven, Belgium, 14-16 December 1994, Proceedings</i>. Lecture Notes in Computer Science. Vol. 1008. Springer. pp. <span class="nowrap">275–</span>285. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-60590-8_21">10.1007/3-540-60590-8_21</a></span>.</cite></span>

</li>

<li id="cite_note-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-16">^</a></b></span> <span class="reference-text"><cite id="CITEREFDaemen1998" class="citation web cs1">Daemen, Joan (10 June 1998). <a rel="nofollow" class="external text" href="https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf">"Chapter 5: Propagation and Correlation - Annex to AES Proposal Rijndael"</a> <span class="cs1-format">(PDF)</span>. <i>NIST</i>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20180723015757/https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Standards-and-Guidelines/documents/aes-development/PropCorr.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2018-07-23.</cite></span>

</li>

<li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><cite id="CITEREFNyberg2019" class="citation web cs1">Nyberg, Kaisa (December 1, 2019). <a rel="nofollow" class="external text" href="https://eprint.iacr.org/2019/1381.pdf">"The Extended Autocorrelation and Boomerang Tables and Links Between Nonlinearity Properties of Vectorial Boolean Functions"</a> <span class="cs1-format">(PDF)</span>. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201102023321/https://eprint.iacr.org/2019/1381.pdf">Archived</a> <span class="cs1-format">(PDF)</span> from the original on 2020-11-02.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFCramaHammer2011" class="citation cs2">Crama, Yves; <a href="Peter_L._Hammer" title="Peter L. Hammer">Hammer, Peter L.</a> (2011), <i>Boolean Functions: Theory, Algorithms, and Applications</i>, Cambridge University Press, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511852008">10.1017/CBO9780511852008</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780511852008</bdi></cite></li>

<li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Boolean_function">"Boolean function"</a>, <i><a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a></i>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><cite id="CITEREFJankovićStankovićMoraga2003" class="citation journal cs1">Janković, Dragan; Stanković, Radomir S.; Moraga, Claudio (November 2003). <a rel="nofollow" class="external text" href="https://doi.org/10.2298%2FSJEE0301071J">"Arithmetic expressions optimisation using dual polarity property"</a>. <i>Serbian Journal of Electrical Engineering</i>. <b>1</b> (<span class="nowrap">71–</span>80, number 1): <span class="nowrap">71–</span>80. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.2298%2FSJEE0301071J">10.2298/SJEE0301071J</a></span>.</cite></li>

<li><cite id="CITEREFArnold2011" class="citation book cs1">Arnold, Bradford Henry (1 January 2011). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=KoAsmTsOK9IC&q=%22boolean+function%22"><i>Logic and Boolean Algebra</i></a>. Courier Corporation. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-486-48385-6</bdi>.</cite></li>

<li><cite id="CITEREFManoCiletti2013" class="citation cs2">Mano, M. M.; Ciletti, M. D. (2013), <i>Digital Design</i>, Pearson</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)<br> and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>/<a href="Surjective_function" title="Surjective function">Sur</a>/<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems"><span style="font-size: 85%;">list</span></a>),<br><a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Finitary_relation" title="Finitary relation">Relation</a></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic<br>systems</a> <span style="font-size: 85%;">(<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements"><i>Elements</i></a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><i><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_function" title="Computable function">Computable function</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="skin-invert-image noviewer" typeof="mw:File"></span> </span><a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div> <div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Function330" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Function330" style="font-size:114%;margin:0 4em"><a href="Function_(mathematics)" title="Function (mathematics)">Function</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="History_of_the_function_concept" title="History of the function concept">History</a></li>

<li><a href="List_of_mathematical_functions" title="List of mathematical functions">List of specific functions</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types by domain and codomain</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Classes/properties</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Constant_function" title="Constant function">Constant</a></li>

<li><a href="Identity_function" title="Identity function">Identity</a></li>

<li><a href="Linear_map" title="Linear map">Linear</a></li>

<li><a href="Polynomial" title="Polynomial">Polynomial</a></li>

<li><a href="Rational_function" title="Rational function">Rational</a></li>

<li><a href="Algebraic_function" title="Algebraic function">Algebraic</a></li>

<li><a href="Analytic_function" title="Analytic function">Analytic</a></li>

<li><a href="Smooth_function" class="mw-redirect" title="Smooth function">Smooth</a></li>

<li><a href="Continuous_function" title="Continuous function">Continuous</a></li>

<li><a href="Measurable_function" title="Measurable function">Measurable</a></li>

<li><a href="Injective_function" title="Injective function">Injective</a></li>

<li><a href="Surjective_function" title="Surjective function">Surjective</a></li>

<li><a href="Bijection" title="Bijection">Bijective</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Constructions</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Restriction_(mathematics)" title="Restriction (mathematics)">Restriction</a></li>

<li><a href="Function_composition" title="Function composition">Composition</a></li>

<li><a href="Inverse_function" title="Inverse function">Inverse</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Generalizations</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a> (<a href="Binary_relation" title="Binary relation">Binary relation</a>)</li>

<li><a href="Set-valued_function" title="Set-valued function">Set-valued</a></li>

<li><a href="Multivalued_function" title="Multivalued function">Multivalued</a></li>

<li><a href="Partial_function" title="Partial function">Partial</a></li>

<li><a href="Implicit_function" title="Implicit function">Implicit</a></li>

<li><a href="Function_space" title="Function space">Space</a></li>

<li><a href="Higher-order_function" title="Higher-order function">Higher-order</a></li>

<li><a href="Morphism" title="Morphism">Morphism</a></li>

<li><a href="Functor" title="Functor">Functor</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-19" href="https://en.wikipedia.org/wiki/?title=Boolean_function&oldid=1296413089">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>